//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 动态规划 回溯 
// 👍 2429 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new GenerateParentheses().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 输入整数n，返回能够生成的所有有效的括号组合
         */
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            StringBuilder s = new StringBuilder("(");
            dfs(1, 0, s, res, n);
            return res;
        }
        /**
         *
         * @param left 左括号的数量，最初传入时为1，因为第一个必须是(
         * @param right 右括号的数量
         * @param s 拼接结果
         * @param res 返回值
         * @param n 括号对数
         */
        public void dfs(int left, int right, StringBuilder s, List<String> res, int n){
            if (left == n && right == n) res.add(s.toString());// 这说明左括号和右括号都添加完了
            else {
                if (right > left) return;
                if (left < n){// 优先添加左括号
                    s.append("(");
                    dfs(left + 1, right, s, res, n);
                    s.deleteCharAt(s.length() - 1);// 回溯，删除刚刚添加的左括号
                }
                if(right < n){// 添加右括号
                    s.append(")");
                    dfs(left, right + 1, s, res, n);
                    s.deleteCharAt(s.length() - 1);// 回溯，删除刚刚添加的右括号
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}